package jiaoheng.数据结构;

import org.junit.Test;

public class s2链表 {


    @Test
    public void testIterator(){
        LinkList linkList = new LinkList();
        linkList.init();
        linkList.printList();
        System.out.println("\n=================");

        linkList.reverse();
        linkList.printList();
        System.out.println("\n=================");

        linkList.reverseRecursive();
        linkList.printList();
    }
}
class Node{
    int val;
    Node next;
    public Node(int v){
        this.val = v;
    }
}
class LinkList{
    Node head;

    public void init(){
        this.head = new Node(1);
        this.head.next = new Node(2);
        this.head.next.next = new Node(3);
        this.head.next.next.next = new Node(4);
        this.head.next.next.next.next = new Node(5);
    }
    // 打印
    public void printList(){
        Node current = head;
        while(current!=null){
            System.out.print(current.val+" ");
            current = current.next;
        }
    }
    // 反转,current pre next
    public void reverse(){
        if(head==null){
            return;
        }
        Node next;
        Node pre = null;
        Node current = head;
        while(current!=null){
            next = current.next;
            current.next=pre;
            pre = current;
            current = next;

        }
        head = pre;
    }

    public void reverseRecursive(){
        head = reverseRecursive(head);
    }

    // 反转,current pre next
    private Node reverseRecursive(Node headNode){
        if (headNode == null || headNode.next == null) {
            return headNode; // 基本情况：空链表或只有一个节点
        }
        Node newHead = reverseRecursive(headNode.next); // 获取新的头节点

        // 真正处理指针的操作
        headNode.next.next = headNode;
        headNode.next = null;

        return newHead;
    }
}
